import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * Description: 优选算法 day3
 * User: 姚东名
 * Date: 2024-12-09
 * Time: 13:39
 */
public class Test {
    // 11. 最⼤连续 1 的个数 III（medium）
    public static int longestOnes(int[] nums, int k) {
        int left = 0;
        int right = 0;
        int zeroCount = 0;
        int maxLength = 0;
        // 开始滑动窗口来遍历数组
        while (right < nums.length) {
            // 记录最长数组零的个数
            if (nums[right] == 0) {
                zeroCount++;
            }
            while (zeroCount > k) {
                // left出窗口,出到0符合k的个数
                if (nums[left] == 0) {
                    zeroCount--;
                }
                left++;
            }
            // 更新操作
            maxLength = Math.max(maxLength, right - left + 1);
            right++;
        }
        return maxLength;
    }

    public static void main1(String[] args) {
        int[] nums = {1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0};
        int k = 2;
        System.out.println(longestOnes(nums, k));

        int[] nums2 = {0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1};
        int k2 = 3;
        System.out.println(longestOnes(nums2, k2));
    }

    // 12. 将 x 减到 0 的最⼩操作数 (medium)
    public static int minOperations(int[] nums, int x) {
        // 将数组中元素和加起来
        int sum = 0;
        for(int num : nums) {
            sum += num;
        }
        // 第二步：优化
        int target = sum - x;
        if (target  < 0) {
            return -1;
        }
        // 刚刚x与总数sum相等
        if (target == 0) {
            return nums.length;
        }

        int left = 0;
        int curSum = 0;
        int minOp = Integer.MAX_VALUE;
        for (int right = 0; right < nums.length; right++) {
            // 入窗口
            curSum += nums[right];
            /**
             * 调整窗口（收缩窗口）：
             * 当curSum大于目标和target时，需要收缩窗口，
             * 也就是通过while (curSum > target && left <= right)循环，
             * 从窗口左边移除元素，即将nums[left]从curSum中减去（curSum -= nums[left]），
             * 然后左移left指针（left++），直到窗口内元素和不大于目标和为止。
             */
            while (left <= right && curSum > target) {
                // 出窗口
                curSum -= nums[left];
                left++;
            }
            // 更新结果
            if (curSum == target) {
                minOp = Math.min(minOp, nums.length - (right - left + 1));
            }
        }
        return minOp == Integer.MAX_VALUE ? -1 : minOp;
    }

    public static void main2(String[] args) {
        int[] nums = {1, 1, 4, 2, 3};
        int x = 5;
        System.out.println(minOperations(nums, x));

        int[] nums2 = {5, 6, 7, 8, 9};
        int x2 = 4;
        System.out.println(minOperations(nums2, x2));

        int[] nums3 = {3, 2, 20, 1, 1, 3};
        int x3 = 10;
        System.out.println(minOperations(nums3, x3));
    }

    public static int totalFruit(int[] fruits) {
        int left = 0;
        int maxFruits = 0;
        Map<Integer, Integer> fruitCount = new HashMap<>();

        for (int right = 0; right < fruits.length; right++) {
            // 将水果放进篮子中，统计水果个数和种类
            // fruitCount.put(fruits[right], fruitCount.getOrDefault(fruits[right], 0) + 1)，
            // 意思是如果该水果种类已经在map中存在，就获取其当前数量并加 1；如果不存在，则初始化为 1。
            fruitCount.put(fruits[right], fruitCount.getOrDefault(fruits[right], 0) + 1);
            // 当水果的种类超过2中的时候，就要收缩窗口 left向前走
            while (fruitCount.size() > 2) {
                fruitCount.put(fruits[left], fruitCount.get(fruits[left]) - 1);
                // 当某种水果数量达到0时，删除该水果种类
                if (fruitCount.get(fruits[left]) == 0) {
                    fruitCount.remove(fruits[left]);
                }
                left++;
            }
            // 更新结果
            maxFruits = Math.max(maxFruits, right - left + 1);
        }
        return maxFruits;
    }

    public static void main3(String[] args) {
        int[] fruits = {1, 2, 1};
        System.out.println(totalFruit(fruits));

        int[] fruits2 = {0, 1, 2, 2};
        System.out.println(totalFruit(fruits2));

        int[] fruits3 = {3, 3, 3, 1, 2, 1, 1, 2, 3, 3, 4};
        System.out.println(totalFruit(fruits3));
    }

    // 14. 找到字符串中所有字母异位词
    public static List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        if (s.length() < p.length()) {
            return result;
        }

        // 用于统计字符串p中各字符出现的次数
        Map<Character, Integer> targetMap = new HashMap<>();
        for (char c : p.toCharArray()) {
            targetMap.put(c, targetMap.getOrDefault(c, 0) + 1);
        }

        // 用于统计滑动窗口内各字符出现的次数
        Map<Character, Integer> windowMap = new HashMap<>();
        int left = 0;
        int right = 0;
        int matchCount = 0;

        while (right < s.length()) {
            char rightChar = s.charAt(right);
            // 将窗口右移一位，把新进入窗口的字符加入统计
            windowMap.put(rightChar, windowMap.getOrDefault(rightChar, 0) + 1);
            // 如果窗口内该字符出现次数不超过目标字符串中该字符出现次数，则匹配字符数加1
            if (windowMap.get(rightChar) <= targetMap.getOrDefault(rightChar, 0)) {
                matchCount++;
            }
            // 当窗口大小等于目标字符串长度时，判断是否为异位词
            if (right - left + 1 == p.length()) {
                if (matchCount == p.length()) {
                    result.add(left);
                }
                char leftChar = s.charAt(left);
                // 将窗口左移一位，把移出窗口的字符从统计中移除
                windowMap.put(leftChar, windowMap.get(leftChar) - 1);
                // 如果窗口内该字符出现次数小于目标字符串中该字符出现次数，匹配字符数减1
                if (windowMap.get(leftChar) < targetMap.getOrDefault(leftChar, 0)) {
                    matchCount--;
                }
                left++;
            }
            right++;
        }
        return result;
    }

    public static void main(String[] args) {
        String s = "cbaebabacd";
        String p = "abc";
        List<Integer> res = findAnagrams(s, p);
        System.out.println(res);

        String s2 = "abab";
        String p2 = "ab";
        List<Integer> res2 = findAnagrams(s2, p2);
        System.out.println(res2);
    }
}
